34. Слово спонсора

По завершению турнира “Новогодняя ночь” спонсор решил отправить m призерам подарки по почте. Зная количество участников n и время доставки почты между некоторыми отделениями “Укрпочты”, найти, через какое время последний из призеров получит свой приз.

Вход. Первая строка содержит 3 числа: количество участников турнира n, количество призов спонсора m и количество известных временных сроков доставки между некоторыми из отделений k. В следующей строке через пробел указаны номера участников, ставших призёрами.

Далее идет k строк по 3 числа в каждой с информацией об известных сроках доставки между некоторыми из отделений в формате: a b t, где a и b – номера отделений, t (0 ≤ t ≤ 365) – время доставки почты между ними. В последней строке находится единственное число – номер почтового отделения, из которого спонсор будет отправлять призы. Известно, что 1 ≤ n, m, a, b ≤ 365.

Выход. Если все призы будут доставлены участникам – вывести в первой строке “The good sponsor!”, а в следующей – время, через какое последний из призеров получит свой приз. Если хотя бы один из участников не сможет получить приз – вывести в единственной строке “It is not fault of sponsor...”. Фразы выводить без кавычек.

Пример входа	Пример выхода
3 2 2 2 3 1 2 3 2 3 4 1	The good sponsor! 7

РЕШЕНИЕ

графы – алгоритм Дейкстры

Анализ алгоритма

Рассмотрим граф, вершинами которого будут почтовые отделения, а весами ребер – время доставки между ними. В задаче необходимо найти длины кратчайших путей от почтового отделения, из которого спонсор отправляет призы, до участников – призеров. Это можно совершить при помощи алгоритма Дейкстры. Время, через которое последний из призеров получит свой приз, равно максимуму среди найденных длин кратчайших путей.

Пример

Рассмотрим граф, приведенный в условии. Спонсор отправляет призы из вершины 1. Призеры расположены в вершинах 2 и 3.

Реализация алгоритма

Объявим константы и массивы для реализации алгоритма Дейкстры. Номера участников, ставших призёрами, занесем в массив priz.

#define MAX 400

#define INF 0x3F3F3F3F

int mas[MAX][MAX], used[MAX], d[MAX];

int priz[MAX];

Читаем входные данные.

scanf("%d %d %d",&n,&m,&k);

for(i = 1; i <= m; i++) scanf("%d",&priz[i]);

Строим входной граф. Инициализируем переменные.

memset(mas,63,sizeof(mas));

memset(used,0,sizeof(used));

for(i = 1; i <= k; i++)

{

scanf("%d %d %d",&b,&e,&dist);

mas[b][e] = mas[e][b] = dist;

}

memset(d,0x3F,sizeof(d));

scanf("%d",&source);

d[source] = 0;

Запускаем алгоритм Дейкстры.

for(i = 1; i < n; i++)

{

min = INF;

for(j = 1; j <= n; j++)

if (!used[j] && d[j] < min) {min = d[j]; w = j;}

for(j = 1; j <= n; j++)

if (!used[j]) d[j] = minimum(d[j],d[w] + mas[w][j]);

used[w] = 1;

}

Ищем наибольшее время, через которое все призеры получат свои призы.

mx = 0;

for(i = 1; i <= m; i++)

if (d[priz[i]] > mx) mx = d[priz[i]];

Если это время равно бесконечности, то кто-то из участников приз не получит.

if (mx == INF) printf("It is not fault of sponsor...\n");

else printf("The good sponsor!\n%d\n",mx);

Java реализация

import java.util.*;

public class Main

{

static final int INFINITY = 2000000000;

static int g[][], used[], dist[], priz[];

static void Relax(int i, int j)

{

if (dist[i] + g[i][j] < dist[j])

dist[j] = dist[i] + g[i][j];

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

int m = con.nextInt();

int k = con.nextInt();

g = new int[n+1][n+1];

for (int[] row: g) Arrays.fill(row, INFINITY);

priz = new int[n+1];

for(int i = 1; i <= m; i++)

priz[i] = con.nextInt();

for (int i = 1; i <= k; i++)

{

int b = con.nextInt();

int e = con.nextInt();

int dist = con.nextInt();

g[b][e] = g[e][b] = dist;

}

used = new int[n+1];

dist = new int[n+1]; Arrays.fill(dist, INFINITY);

int source = con.nextInt();

dist[source] = 0;

for (int i = 1; i < n; i++)

{

// find vertex w with minimum d[w] among not used vertices

int min = INFINITY, v = -1;

for (int j = 1; j <= n; j++)

if (used[j] == 0 && dist[j] < min) { min = dist[j]; v = j; }

// no more vertices to add

if (v < 0) break;

// relax all edges outgoing from v

// process edge v -> j

for (int j = 1; j <= n; j++)

if (used[j] == 0) Relax(v, j);

// shortest distance to v is found

used[v] = 1;

}

int max = 0;

for(int i = 1; i <= m; i++)

if (dist[priz[i]] > max) max = dist[priz[i]];

if (max == INFINITY) System.out.println("It is not fault of sponsor...");

else System.out.println("The good sponsor!\n" + max);

con.close();

}

}